#include <iostream>
#include <cstdlib>
#include <utility>
#include <string>
#include <vector>

template <typename... Ts>
constexpr void print(const Ts&... args) {
	(std::cout << ... << (args));
	std::cout.flush();
}

/*
	supports integer number
	operator: +, -, *, /, %, (, )
*/
using namespace std::literals;

enum operator_category {
	ADD = 0, MNS, MUL, DIV, MOD, LP, RP, 
	NOT_A_OPER = -1,
	UNKNOWN = -2
};

static constexpr char oper_table[] = {
	'+', '-', '*', '/', '%', '(', ')'
};

struct token {
	long long value = 0;
	operator_category oper = UNKNOWN;

	token() = default;
	token(long long value_) noexcept: value{value_}, oper{NOT_A_OPER} {}
	token(operator_category oper_) noexcept: oper{oper} {}
	token(char c) noexcept{
		switch(c) {
			case '+': oper = ADD; break;
			case '-': oper = MNS; break;
			case '*': oper = MUL; break;
			case '/': oper = DIV; break;
			case '%': oper = MOD; break;
			case '(': oper = LP;  break;
			case ')': oper = RP;  break;
			default:  oper = UNKNOWN;
		}
	}

	explicit operator std::string() const{
		if(oper == UNKNOWN)         return {'?'};
		else if(oper == NOT_A_OPER) return std::to_string(value);
		else                        return {oper_table[oper]};
	}
};

struct astnode {
	token tok;
	astnode* v1 = nullptr, 
	       * v2 = nullptr;

	astnode() = default;
	astnode(astnode&& node) noexcept: tok{node.tok}, v1{node.v1}, v2{node.v2} {
		node.tok = {};
		node.v1 = nullptr;
		node.v2 = nullptr;
	}
	astnode(const astnode& node): tok{node.tok} {
		if(node.v1 != nullptr) v1 = new astnode{*node.v1};
		if(node.v2 != nullptr) v2 = new astnode{*node.v2};
	}
	
	astnode(const token& tok_, astnode&& v1_, astnode&& v2_) noexcept: 
		tok{tok_}, v1{new astnode{std::move(v1_)}}, v2{new astnode{std::move(v2_)}} {
	} 

	astnode(const token& tok_, const astnode& v1_, const astnode& v2_): 
		tok{tok_}, v1{new astnode{v1_}}, v2{new astnode{v2_}} {
	}

	astnode(const token& tok_) noexcept: tok{tok_} {} 

	~astnode() {
		//if tok.oper == NOT_A_OPER, then it's always v1 == v2 == nullptr
		delete v1;
		delete v2;
	}

	void dispose() {
		delete v1;
		delete v2;
		v1 = nullptr;
		v2 = nullptr;
		tok = {};	
	}

	astnode& operator=(const astnode& node) {
		if(&node == this) return *this;
		auto v1_ = new astnode{*node.v1};
		auto v2_ = new astnode{*node.v2};
		delete v1;
		delete v2;
		tok = node.tok;
		v1 = v1_;
		v2 = v2_;
		return *this;
	}
	astnode& operator=(astnode&& node) noexcept{
		if(&node == this) return *this;
		tok = node.tok;
		delete v1;
		delete v2;
		v1 = v2 = nullptr;
		std::swap(v1, node.v1);
		std::swap(v2, node.v2);
		return *this;
	}

	std::string to_string(int align_len = 0) const{
		if(tok.oper == NOT_A_OPER) {
			return std::string(align_len, '\t') + std::to_string(tok.value);
		}else {
			auto s = v1->to_string(align_len + 1);
			s.push_back('\n');
			s.append(align_len, '\t');
			s.push_back(oper_table[tok.oper]);
			s.push_back('\n');
			s.append(v2->to_string(align_len + 1)).push_back('\n');
			return s;
		}
	}

};

std::pair<std::vector<token>, const char*> lex(const char* s) {
	if(!s) return {{}, s};
	auto res = std::pair<std::vector<token>, const char*>{{}, s};
	const char* pos = s;
	while(*pos != '\0') {
		switch(*pos) {
			case '\x9' ... '\xd': [[fallthrough]]; // '\t' '\n' '\v' '\f' '\r' 
			case ' ': 
				//spaces
				++pos; //skip white spaces
				break;
			case '0' ... '9':
				//number
				res.first.emplace_back(std::strtoll(pos, const_cast<char**>(&pos), 0));
				break;
			case '+':[[fallthrough]];
			case '-':[[fallthrough]];
			case '*':[[fallthrough]];
			case '/':[[fallthrough]];
			case '%':[[fallthrough]];
			case '(':[[fallthrough]];
			case ')':
				res.first.emplace_back(*pos);
				++pos;
				break;
			default:
				res.second = pos;
				return res;
		}
	}
	res.second = pos;
	return res;
}

void reduce(const token& op, std::vector<astnode>& nums) {
	//assume nums.size() >= 2

	astnode n2{std::move(nums.back())};
	nums.pop_back();
	
	astnode n1{std::move(nums.back())};
	nums.pop_back();

	nums.emplace_back(op, std::move(n1), std::move(n2));
}


std::pair<astnode, const char*> pas(const std::vector<token>& tokens) {
	if(tokens.empty()) return {{}, ""};

	//shunting yard algo
	std::vector<token> opers;
	std::vector<astnode> outs;

	//ADD = 0, MNS, MUL, DIV, MOD, LP
	//+        -    *    /    %    (
	static constexpr int priority[] = {1, 1, 2, 2, 2, 0};
	for(const auto& i: tokens) {
		if(i.oper == NOT_A_OPER) {
			//is a number
			outs.emplace_back(i);
		}else if(i.oper == RP) {
		while(!opers.empty() and opers.back().oper != LP) {

				//reduce
				if(outs.size() < 2) {
				return {{}, "error at parsing: too few operands in parentess"};
				}
				reduce(opers.back(), outs);
				opers.pop_back();
			}
			opers.pop_back();  //pop (
		}else if(i.oper == LP or opers.empty() or priority[opers.back().oper] < priority[i.oper]) {
			//shift-in
			opers.push_back(i);
		}else {
			do{
				//reduce
				if(outs.size() < 2) {
					return {{}, "error at parsing: too few operands(case 1)"};
				}

				reduce(opers.back(), outs);
	
				opers.pop_back();
			}while(!opers.empty() and priority[opers.back().oper] >= priority[i.oper]);
			opers.push_back(i);
	
		}
	}

	while(!opers.empty()) {
		if(outs.size() < 2) {
			return {{}, "error at parsing: too few operands(case 2)"};
		}
		reduce(opers.back(), outs);
		opers.pop_back();
	}
	if(outs.size() != 1) {
		return {{}, "error at parsing: too many operands"};
	}
	return {std::move(outs.front()), nullptr};
}

long long eval(const astnode& root) {
	switch(root.tok.oper) {
	case NOT_A_OPER:
		return root.tok.value;
	case ADD:
		return eval(*root.v1) + eval(*root.v2);
	case MNS:
		return eval(*root.v1) - eval(*root.v2);
	case MUL:
		return eval(*root.v1) * eval(*root.v2);
	case DIV:
		return eval(*root.v1) / eval(*root.v2);
	case MOD:
		return eval(*root.v1) % eval(*root.v2);
	default:
		return 0;
	}
}

int main() {
	using std::cout;
	std::string target = "0 - 7 * (32 + 2 % (349 / 2 + (3) - 5)) / 78 ";
	auto lexed = lex(target.data()).first;
	for(const auto& i : lexed) cout << std::string(i) << " ";
	cout << '\n';
	auto parsed = pas(lexed);
	if(parsed.second != nullptr) cout << parsed.second;
	else {
		std::cout << parsed.first.to_string();	
		print("result = ", eval(parsed.first), '\n');
	}

}

